package Algorithm.Sort;

//选择排序,时间复杂度为O（N2），冒泡的改进版
public class SelctionSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 8, 7, 26, 13, 42, 36, 99};
        printArray(arr);
        function(arr);
        printArray(arr);
    }

    public static void function(int[] arr) {
        //与冒泡的区别：每一次循环的时候，找到最小的一个数，将这个数与排序序列的最后一个交换。而冒泡是找到一个交换一个。
        //虽然最坏情况下也是要O（N2），但是其他情况下比冒泡要效率高，减少了很多排序。
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(arr[i], arr[minIndex]);
            }
        }
    }


    //工具方法，顺序打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    //工具方法，交换两个数
    public static void swap(int n, int m) {
        int temp = n;
        n = m;
        m = temp;
    }
}
